package Year21_Month11.day1122;

public class TreeMap<K extends Comparable<K>,V> implements Map<K,V>{
    //定义TreeNode节点
    public static class TreeNode<K,V>{
        TreeNode left;
        TreeNode right;
        Map.Entry<K,V> kv;

        public TreeNode(K key,V value){
            kv = new Entry<>();
            kv.key = key;
            kv.value = value;
        }
    }
    //接着定义根节点
    TreeNode<K,V> root = null;
    int size = 0;


    @Override
    public V put(K key, V value) {
        //这种是节点为null的情况
        if(root == null){
            root = new TreeNode<>(key,value);
            size++;
            return value;
        }
        //接下来对插入位置进行查找,如果下标的节点已经存在就覆盖，不存在的话就要用parent进行来进行标志插入
        TreeNode<K,V> cur = root;
        TreeNode<K,V> parent = null;
        while(cur != null){
            parent = cur;
            int fac = key.compareTo(cur.kv.key);//下标进行比较
            if(fac > 0) {
                cur = cur.right;
            }else if(fac < 0){
                cur = cur.left;
            }else{
                V oldValue = cur.kv.value;
                cur.kv.value = value;
                return oldValue;
            }
        }
        //要插入节点在树中不存在所以不存在覆盖这种情况，就有了以下对左右子树插入情况的判断
        int res = key.compareTo(parent.kv.key);
        TreeNode<K,V> fac = new TreeNode<>(key,value);
        if(res > 0){
            parent.right = fac;
        }else{
            parent.left = fac;
        }
        size++;
        return value;
    }

    @Override
    public V get(K key) {
        TreeNode<K,V> cur = root;
        while(cur != null){
            int val = key.compareTo(cur.kv.key);
            if(val > 0){
                cur = cur.right;
            }else if(val < 0){
                cur = cur.left;
            }else{
                return cur.kv.value;
            }
        }
        return null;
    }

    @Override
    public V getOrDefault(K key, V value) {
        //先定义本身的value值
        V node  = get(key);
        //如果为null就返回你传入的value值，不为null就返回本身的value值
        return node == null ? value : node;
    }

    @Override
    public V remove(K key) {
        TreeNode<K,V> cur = root;
        TreeNode<K,V> parent = null;
        while(cur != null){
            int res = key.compareTo(cur.kv.key);
            if(res > 0){
                parent = cur;
                cur = cur.right;
            }else if(res < 0){
                parent = cur;
                cur = cur.left;
            }else{
                break;
            }
        }
        if(cur == null){
            return null;
        }
        V val = cur.kv.value;
        //那接下来待删除节点已经找到，开始进行删除
        if(cur.left == null){//左子树为空的情况
            if(parent == null){//如果是根节点
                root = cur.right;
            }else{//不是根节点
                if(cur == parent.left){
                    parent.left = cur.right;
                }else{
                    parent.right = cur.right;
                }
            }
            cur.right = null;
        }else if(cur.right == null){//右子树为空
            if(parent == null){
                root = cur.left;
            }else{
                if(parent == parent.left){
                    parent.left = cur.left;
                }else{
                    parent.left = cur.left;
                }
            }
            cur.left = null;
        }else{//左右子树都不为空
            TreeNode<K,V> fac = cur.right;
            while(fac.left != null){
                parent = fac;
                fac = fac.left;
            }
            cur.kv = fac.kv;//把右子树最左侧节点覆盖待删除节点
            if(parent.left == fac){
                parent.left = fac.right;
            }else{
                parent.right = fac.right;
            }
        }
        return val;

    }

    @Override
    public boolean containsKey(K key) {
        TreeNode<K,V> cur = root;
        while(cur != null) {
            int fac = key.compareTo(cur.kv.key);
            if(fac == 0){
                return true;
            }else if(fac > 0){
                cur = cur.right;
            }else{
                cur = cur.left;
            }
        }
        return false;
    }

    @Override
    public boolean containsValue(V value) {
        return containsValue(value,root);
    }
    public boolean containsValue(V value,TreeNode<K,V> root) {
        TreeNode<K,V> cur = root;
        if(cur == null){
            return false;
        }
        if(cur.kv.value == value){
            return false;
        }
        return containsValue(value,root.left) || containsValue(value,root.right);
    }

    @Override
    public int size() {
        return size;
    }
}
